//
//  Matrix01.swift
//  LeetCodeDemo
//
//  Created by OS on 2022/6/16.
//

import Foundation

/*
 542. 01 矩阵
 
 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

 两个相邻元素间的距离为 1 。
 
 */

class Matrix01 {
    
    /*
     广度优先搜索
     先将值为0的点加入到队列,0的点距离就是0,相当于距离计算完成了
     将visited访问过的标识赋值1,这样没访问过的位置数值就一定都是1了
     将队列里的值进行四个方向处理,如果发现没有计算过的点,那么就在现有点的距离基础上+1
     并将没有计算过的点加入到队列中,便于后续的继续地毯式搜索
     这样依次将队列中的位置计算完成后就得到了最终的距离矩阵
     */
    func updateMatrix(_ mat: [[Int]]) -> [[Int]] {
        let m = mat.count
        let n = mat[0].count
        var res = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
        var visited = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
        var queue = [[Int]]()
        for i in 0..<m {
            for j in 0..<n {
                if mat[i][j] == 0 {
                    queue.append([i, j])
                    visited[i][j] = 1
                }
            }
        }

        let dx = [-1, 0, 1, 0]
        let dy = [0, -1, 0, 1]
        while !queue.isEmpty {
            let point = queue.removeFirst()
            let x = point[0]
            let y = point[1]
            for i in 0..<4 {
                let mx = x + dx[i]
                let my = y + dy[i]
                if mx >= 0 && mx < m && my >= 0 && my < n && visited[mx][my] != 1 {
                    res[mx][my] = res[x][y] + 1
                    queue.append([mx, my])
                    visited[mx][my] = 1
                }
            }
        }
        return res
    }
}
